import java.util.Arrays;
import java.util.Comparator;

/**
 * Created by L.jp
 * Description:有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。
 * 已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。
 *
 * 示例：
 *
 * 输入：height = [65,70,56,75,60,68] weight = [100,150,90,190,95,110]
 * 输出：6
 * 解释：从上往下数，叠罗汉最多能叠 6 层：(56,90), (60,95), (65,100), (68,110), (70,150), (75,190)

 * User: 86189
 * Date: 2022-05-03
 * Time: 14:46
 */
public class Solution {
    /*  关键点：在上面的人要比下面的人矮一点且轻一点，
    这道题和牛客的马戏团差不多，也就是一个求最长上升子序列的问题，但是我们如果仅仅使用动态规划是解决不了问题的，
    因为常规的动态规划解决最长上升子序列时间复杂度是O（N^2）,而一般面试是要求时间优化的，时间复杂度是O（N*logn) ,其实动态规划+二分查找解决问题
    这道题其实就是对应牛客的最长上升子序列（二）的做法，只不过这里多了一个维度就是既有体重又有身高，我们不能同时对两个维度进行最长上升子序列的求得
    所以我们要先保证一个维度是递增的，再用其他办法求出另一个维度的最长上升子序列
    
    之前我们求最长上升子序列就是使用一个数组存储i之前包括i的最长上升子序列的长度，但是这样时间复杂度比较高，那么对于这个进阶的求最长上升子序列的题
    我们可以采用dp数组存储最长上升子序列的各个元素，那么他的最后一个下标就是最长上升子序列的长度
    * */
    public static int bestSeqAtIndex(int[] height, int[] weight) {
        //由于这个题包含两个维度，所以我们需要对整体进行最长上升子序列的求解，需要那对应的体重和身高包装成一个类的属性，或者直接使用数组存储这两个属性也行
        int n=weight.length;
        //这里我们使用一个二维数组存储两个属性
        int[][] circus=new int[n][2];
        for(int i = 0; i < n; i++){
            circus[i]=new int[]{weight[i],height[i]};
        }
        //然后我们对这个数组进行体重的升序排序，如果体重相同时，身高降序排序的比较规则，利用sort进行排序
        Arrays.sort(circus, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                //int[] 是每一行的元素，有两个属性，0下标对应体重，1下标对应身高
                //实际是体重的升序排序
                int ret=o1[0] - o2[0];
                return ret==0 ? o2[1]-o1[1] : ret; //体重相同时，对身高降序排序
            }
        });
        int[] dp=new int[n]; //存储最长上升子序列元素,最后一个元素始终是数组里最大的
        int end=-1; //dp数组的最后一元素的下标，也就是代表着最长上升子序列的长度
        //然后进行身高的最长上升子序列的查找
        for(int i = 0; i <n;i++){
            if(i==0 || dp[end]<circus[i][1]){
                //如果最长上升子序列数组的最后一个元素小于原数组的身高元素，那么把这个身高元素加入到dp数组
                dp[++end]=circus[i][1];
            }else{
                //如果该身高元素小于dp数组最后一个元素，那么就在dp数组中找到第一个比该元素大的位置，
                // 这个位置就是在原数组中以该元素结尾的最长上升子序列的长度，而且在dp数组中该元素包括以前的元素就是以该元素结尾的最长上升子序列
                
                int index=binarySearch(circus[i][1],dp,end);
                dp[index]=circus[i][1];
            }
        }
        //返回数组的长度就是最长上升子序列长度
        return end+1;
    }
    public static int binarySearch(int target,int[] dp,int end){
        int l=0;
        int r=end;
        while (l<r){
            int mid=(l+r)/2;
            if(dp[mid]<target){
                l=mid+1;
            }else{
                r=mid;
            }
        }
        return l;
    }
    
    public static void main(String[] args) {
        int[] height={65,70,56,75,60,68};
        int[] weight={100,150,90,190,95,110};
        System.out.println(bestSeqAtIndex(height, weight));
    }
}
